public class MatrixOrder {
    /**
     * 矩阵连乘问题，利用动态规划求解
     *
     * 记录此时的矩阵连乘的运算次数，假设为dp[i][j]是i行j列的元素的连乘所需的最小
     * 次数，问题的最优解是dp[i][k]+dp[k+1][j]+i-1*k*j的最小值;
     * 递归公式得到的矩阵的对角线上的元素为0
     */
    // p 是一个整数数组，表示一系列矩阵的维度。例如，对于矩阵链 A1 * A2 * A3 * A4，p 的值为 [A1的行数, A2的行数, A3的行数, A4的行数]。
    public static int matrixChainOrder(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    // 找到矩阵中间的过渡,也就是是否有可优化的分割点存在
                    int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k+1] * p[j+1];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        return dp[0][n - 1]; //从第1个矩阵乘以最后一个矩阵
    }

    public static void main(String[] args) {
        int[] p = {5,7,4,3,5}; //4个矩阵的维度
        int minCost = matrixChainOrder(p);
        System.out.println("Minimum cost of matrix chain multiplication: " + minCost);
    }


   /* *//**
     * 求解最优值
     * @param p: 矩阵维数信息数组
     * @param m: 存放最优值数组, 上三角形式
     * @param s: 存放分割位置下标的数组
     * @return 返回最优值
     **//*
    public static int matrixChain(int[] p, int[][] m, int[][] s) {
        int n = p.length - 1;
        for (int i = 1; i <= n; i++)
            // 本身为0
            m[i][i] = 0;  // 初始化二维数组

        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                // 先以i进行划分
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];  // 求出Ai到Aj的连乘
                s[i][j] = i;  // 记录划分位置
                for (int k = i + 1; k < j; k++) {
                    // 寻找是否有可优化的分割点
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];  // 公式
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m[1][n];
    }

    *//**
     * 输出 A[i:j] 的最优计算次序
     * @param i、j: 连乘矩阵下标
     * @param s: 存放分割位置下标的数组
     **//*
    public static void traceback(int i, int j, int[][] s) {
        // 输出A[i:j] 的最优计算次序
        if (i == j) {
            // 递归出口
            System.out.print("A"+i);
            return;
        } else {
            System.out.print("(");
            // 递归输出左边
            traceback(i, s[i][j], s);
            // 递归输出右边
            traceback(s[i][j] + 1, j, s);
            System.out.print(")");
        }
    }

    public static void main(String[] args) {
        int[] p = new int[]{5, 7, 4, 3, 5};
        int[][] m = new int[p.length][p.length];
        int[][] s = new int[p.length][p.length];
        System.out.println("最优值为： "+matrixChain(p, m, s));
        traceback(1, p.length-1, s);
    }*/

}
